package 排序.堆排序;

import java.util.Arrays;

public class mergeSort {
    public static void mergeSortMethod(int[] arr){
        if (arr.length< 2||arr ==null){
            return;
        }
        mergeSortProgress(arr,0, arr.length-1);

    }
    public static void mergeSortProgress(int[] arr,int l, int r){
        if (l==r){
            return;
        }
        int mid = l +((r-l)>>2);
        mergeSortProgress(arr,l,mid);
        mergeSortProgress(arr,mid+1,r);
        merge(arr,l,r,mid);
    }
    public static void merge(int[] arr,int l,int r,int mid){
        int[] tempArray = new int[r-l+1];
        int p1 = l,p2 = mid+1,i=0;
        while (p1 <= mid && p2 <= r){
            tempArray[i++] = arr[p1]<arr[p2] ? arr[p1++] :arr[p2++];
        }
        while (p1 <=mid){
            tempArray[i++]= arr[p1++];
        }
        while (p2 <=r){
            tempArray[i++] = arr[p2++];
        }
        for ( i = 0; i < tempArray.length; i++) {
            arr[l+i] = tempArray[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,3,2,5,8,4,7,6,9};
        mergeSortMethod(arr);
        System.out.println(Arrays.toString(arr));
    }
}
